from typing import *


class Solution:

    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
        letters = {
            2: "abc",
            3: "def",
            4: "ghi",
            5: "jkl",
            6: "mno",
            7: "pqrs",
            8: "tuv",
            9: "wxyz",
        }
        res = []

        def dfs(digits, letters, path, index, res):
            if index == len(digits):
                res.append(path)
                return
            for char in letters[int(digits[index])]:
                dfs(digits, letters, path + char, index + 1, res)
            return

        dfs(digits, letters, '', 0, res)
        return res

if __name__=="__main__":
    sol = Solution()
    sol.letterCombinations("2345")